package week09

// 773. 滑动谜题
// https://leetcode-cn.com/problems/sliding-puzzle/

func slidingPuzzle(board [][]int) int {
	var start = marshal(board)
	var target = 123450
	if start == target {
		return 0
	}

	var dist = make(map[int]int)
	dist[start] = 0

	var queue = &BinaryHeap{}
	queue.push(newNode(eval(board), start))

	var update = func(grid [][]int, state int, x, y, nx, ny int) {
		grid[x][y], grid[nx][ny] = grid[nx][ny], grid[x][y]
		next := marshal(grid)
		if _, ok := dist[next]; !ok || dist[next] > dist[state]+1 {
			dist[next] = dist[state] + 1
			queue.push(newNode(dist[next] + eval(grid), next))
		}
		grid[x][y], grid[nx][ny] = grid[nx][ny], grid[x][y]
	}

	for !queue.empty() {
		state := queue.pop().state
		if state == target {
			return dist[target]
		}

		grid := unmarshal(state)
		x, y := getZeroPos(grid)

		if x > 0 {
			update(grid, state, x, y, x-1, y)
		}
		if x < 1 {
			update(grid, state, x, y, x+1, y)
		}
		if y > 0 {
			update(grid, state, x, y, x, y-1)
		}
		if y < 2 {
			update(grid, state, x, y, x, y+1)
		}
	}
	return -1
}

func eval(grid [][]int) int {
	var res = 0
	for x := range grid {
		for y := range grid[x] {
			if grid[x][y] == 0 {
				continue
			}
			var tx = grid[x][y] / 3
			var ty = (grid[x][y]-tx) % 3
			res = res + abs(tx-x) + abs(ty-y)
		}
	}
	return res
}

func getZeroPos(grid [][]int) (int, int) {
	for i := range grid {
		for j := range grid[i] {
			if grid[i][j] == 0 {
				return i, j
			}
		}
	}
	return -1, -1
}

func marshal(board [][]int) int {
	var state = 0
	for i := range board {
		for j := range board[i] {
			state = state * 10 + board[i][j]
		}
	}
	return state
}

func unmarshal(state int) [][]int {
	var grid = makeGrid()
	for idx := 5; idx >= 0; idx-- {
		grid[idx/3][idx%3] = state % 10
		state /= 10
	}
	return grid
}

func makeGrid() [][]int {
	var grid = make([][]int, 2)
	for i := range grid {
		grid[i] = make([]int, 3)
	}
	return grid
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

type Node struct {
	dist int
	state int
}

func newNode(dist, state int) *Node {
	return &Node{dist, state}
}

type BinaryHeap struct {
	list []*Node
}

func (heap *BinaryHeap) push(val *Node) {
	heap.list = append(heap.list, val)
	var cur = len(heap.list)-1
	var parent = (cur - 1) / 2
	for parent >= 0 {
		if heap.list[parent].dist > heap.list[cur].dist {
			heap.list[parent], heap.list[cur] = heap.list[cur], heap.list[parent]
			cur = parent
			parent = (cur - 1) / 2
		} else {
			break
		}
	}
}

func (heap *BinaryHeap) pop() *Node {
	val := heap.list[0]
	heap.list[0] = heap.list[len(heap.list)-1]
	heap.list = heap.list[:len(heap.list)-1]
	var cur = 0
	var child = cur * 2 + 1
	for child < len(heap.list) {
		var other = cur * 2 + 2
		if other < len(heap.list) && heap.list[child].dist > heap.list[other].dist {
			child = other
		}
		if heap.list[cur].dist > heap.list[child].dist {
			heap.list[cur], heap.list[child] = heap.list[child], heap.list[cur]
			cur = child
			child = cur * 2 + 1
		} else {
			break
		}
	}
	return val
}

func (heap *BinaryHeap) empty() bool {
	return len(heap.list) == 0
}